home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / DClap / DList.cpp < prev    next >
Text File  |  1996-07-05  |  11KB  |  522 lines
  1. // DList.cp
  2. // This code owes it's structure in large part to Apple's MacApp UList unit
  3. // however, d.gilbert has substatially rewritten it.
  4.  
  5.  
  6. #include <ncbi.h>
  7. #include <dgg.h>
  8. #include "DList.h"
  9.  
  10.  
  11. static const short kArrayIncrement = 6;         
  12.  
  13. typedef    DObject* DObjectPtr;
  14.  
  15.  
  16. // class DArray
  17.  
  18.  
  19. DArray::DArray(short itemSize, long initialSize)
  20. {
  21.   SetClass("DArray",sizeof(DArray));
  22.     fArraySize = kEmptySize;
  23.     fArrayIncrement = kArrayIncrement;
  24.     fSize = kEmptySize;
  25.     fArrayStore = NULL;
  26.  
  27.     fItemSize = itemSize;
  28.     fItemSizeShift = 0;
  29.     if (odd(itemSize)) ++itemSize; // make sure we have even size for shifting
  30.     while (((itemSize - 1) >> fItemSizeShift) > 0) ++fItemSizeShift;
  31.     this->SetArraySize(initialSize);
  32. } 
  33.  
  34. DArray::~DArray()
  35. {
  36.     fArrayStore= MemFree(fArrayStore);
  37. }  
  38.  
  39. void DArray::DeleteAll()
  40. {
  41.     if (fSize > kEmptySize) this->DeleteItemsAt(0, fSize); //1,fSize
  42. } 
  43.  
  44. DObject* DArray::Clone()
  45. {
  46.     DArray* result = (DArray*) DObject::Clone();
  47.     result->fArrayStore= MemDup(fArrayStore,  (ulong) (fArraySize << fItemSizeShift));
  48.     return result;
  49. }
  50.  
  51. void* DArray::ComputeAddress(long index)
  52. {
  53.     return (void*) ((char*)fArrayStore + (index << fItemSizeShift)); 
  54. }  
  55.  
  56.  
  57.  
  58. void DArray::DeleteItemsAt(long index, long count)
  59. {
  60.     VoidPtr indexPtr, nextItemPtr, lastItemPtr;
  61.     long countBytes;
  62.  
  63.     countBytes = count << fItemSizeShift;
  64.     indexPtr = this->ComputeAddress(index);
  65.     nextItemPtr = this->ComputeAddress(index + count);
  66.     lastItemPtr = this->ComputeAddress(fSize); //1based: + 1);
  67.  
  68.     if (nextItemPtr < lastItemPtr)        
  69.         MemMove(indexPtr, nextItemPtr, (long)lastItemPtr - (long)nextItemPtr);
  70.  
  71.     this->SetArraySize(fSize - count);        
  72.     fSize -= count;
  73. }   
  74.  
  75.  
  76.  
  77.  
  78. void DArray::GetItemsAt(long index, void* itemPtr, long count)
  79. {
  80.     if (count > kEmptySize)
  81.         MemMove( itemPtr, this->ComputeAddress(index), 
  82.             ((count - 1) << fItemSizeShift) + fItemSize);         
  83. }  
  84.  
  85.  
  86. void DArray::ReplaceItemsAt(long index, void* itemPtr, long count)
  87. {
  88.     VoidPtr indexPtr= this->ComputeAddress(index);
  89.     long countBytes= count << fItemSizeShift;
  90.     MemMove( indexPtr, itemPtr, countBytes);
  91. } 
  92.  
  93.  
  94. void DArray::InsertItemsBefore(long index, void* itemPtr, long count)
  95. {
  96.     VoidPtr indexPtr, nextIndexPtr, lastItemPtr;
  97.     long countBytes;
  98.  
  99.     this->SetArraySize(fSize + count);                 
  100.     indexPtr = this->ComputeAddress(index);
  101.     nextIndexPtr = this->ComputeAddress(index + count);
  102.     lastItemPtr = this->ComputeAddress(fSize);    //1based: fSize + 1
  103.     countBytes = count << fItemSizeShift;
  104.  
  105.     if (index < fSize)        //1based: <=             
  106.         MemMove( nextIndexPtr, indexPtr, (long)lastItemPtr - (long)indexPtr);
  107.  
  108.     if ((countBytes == sizeof(long)) && !odd((long)itemPtr) && !odd((long)indexPtr))
  109.         *((long*)indexPtr) = *((long*)itemPtr);        // shortcut for longs 
  110.     else
  111.         MemMove(indexPtr, itemPtr, countBytes); 
  112.  
  113.     fSize += count;
  114. }  
  115.  
  116.  
  117.  
  118.  
  119. void DArray::SetArraySize(long theSize)
  120. {
  121.     long newSize;
  122.     
  123.     if ((theSize > fArraySize) || (fArraySize - theSize >= fArrayIncrement)) {
  124.         if (fArrayIncrement)
  125.             newSize = (theSize + fArrayIncrement) 
  126.                                 - (theSize + fArrayIncrement) % fArrayIncrement;
  127.         else
  128.             newSize = theSize;
  129.         if (newSize != fArraySize)  {
  130.             ulong chunk= (ulong) (newSize << fItemSizeShift);
  131.             if (fArrayStore == NULL) fArrayStore = MemNew( chunk);
  132.             else fArrayStore= MemMore(fArrayStore, chunk);
  133.             }
  134.         fArraySize = newSize;
  135.       }
  136. } 
  137.  
  138.  
  139. long DArray::Search(CompareFunc compare, void *itemPtr)
  140. {
  141.     register char*  itemAt = (char*) fArrayStore;
  142.     long     itemsize= 1 << fItemSizeShift;
  143.         
  144.         // speed this up w/ a bisection method == start in middle & bounce around ??
  145.         // NO -- can't assume this array is SORTED !!
  146. #if 0
  147.     long lo, hi, mid;
  148.     short cmp;
  149.     lo= 0; 
  150.     hi= fSize;
  151.     do {
  152.         mid= (hi+lo) >> 1;  // div 2;
  153.         itemAt= (char*) fArrayStore + mid * itemsize;
  154.         cmp= (*compare)( itemPtr, itemAt);
  155.         if (cmp == 0) return mid;
  156.         else if (cmp > 0) lo= mid;
  157.         else hi= mid;
  158.     } while (hi > lo+1);
  159.     
  160.     if (mid != hi) {
  161.         itemAt= (char*) fArrayStore + hi * itemsize;
  162.         cmp= (*compare)( itemPtr, itemAt);
  163.         if (cmp == 0) return hi;
  164.         }
  165.     else if (mid != lo) {
  166.         itemAt= (char*) fArrayStore + lo * itemsize;
  167.         cmp= (*compare)( itemPtr, itemAt);
  168.         if (cmp == 0) return lo;
  169.         }
  170.     return kEmptyIndex;
  171. #else
  172.     register long i;
  173.     for (i = 0; i < fSize; i++) {
  174.         if ( (*compare)( itemPtr, itemAt) == 0) 
  175.             return i;
  176.         itemAt += itemsize;
  177.         }
  178.     return kEmptyIndex;
  179. #endif
  180. }     
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188. // class DList
  189.  
  190. // default fCompareFunc
  191. short DefaultCompare(void* item1, void* item2)
  192. {
  193.     if ((unsigned long) item1 > (unsigned long) item2)
  194.         return 1;
  195.     else if ((unsigned long) item1 < (unsigned long) item2)
  196.         return -1;
  197.     else
  198.         return 0;
  199. } 
  200.  
  201.  
  202. DList::DList(CompareFunc itsComparer, short options): 
  203.     DArray(sizeof(DObject*), kEmptySize)
  204. {
  205.   SetClass("DList",sizeof(DList));
  206.     if (itsComparer) fCompareFunc= itsComparer;
  207.     else fCompareFunc= ::DefaultCompare;
  208.     fOwnObjects= options & kOwnObjects;
  209.     fDeleteObjects = options & kDeleteObjects;        
  210. } 
  211.  
  212. DList::~DList()
  213. {
  214.     if (fDeleteObjects) this->FreeAllObjects();
  215. } 
  216.  
  217.         
  218. DObject* DList::At(long index)
  219. {
  220.     //return (*this)[index];
  221.     if (index<0 || index>=fSize) return NULL;
  222.     DObject** vp= (DObject**) ((char*)fArrayStore + (index << fItemSizeShift)); 
  223.     if (vp) return *vp;
  224.     else return NULL;
  225. } 
  226.  
  227.  
  228.  
  229. void DList::FreeAllObjects()
  230. {
  231.     long i, n= this->GetSize();
  232.     for (i= 0; i<n; i++) {
  233.         DObject* obj= At(i);
  234.         if (obj) {
  235.           if (obj->GetOwnerCount() <= 1) delete obj; 
  236.               // ^^^^ BIG MEM LEAK !! THIS delete DOESN"T CALL DESTRUCTOR !
  237.           else obj->suicide(); // this alone doens't call obj destructors !!
  238.           }
  239.         }
  240.     this->DeleteAll();
  241. } 
  242.  
  243.  
  244. long DList::GetEqualItemNo(DObject* item)
  245. {
  246.     long index;
  247.  
  248.     if (item == NULL) return kEmptyIndex;
  249.     index = this->Search( fCompareFunc, &item);
  250.     return index;  // == kEmptyIndex if no match
  251. } 
  252.  
  253.  
  254.  
  255. #if 1
  256. // choose your sort
  257.  
  258. void DList::QuickSort(long beginIndex, long endIndex, CompareFunc CompareItems)
  259. // recursive qs
  260. {
  261.     long i, j;
  262.      DObjectPtr    iobj, jobj, endobj;
  263.      
  264.     if (beginIndex < endIndex) {
  265.         i = beginIndex; 
  266.         j = endIndex;  
  267.         endobj= this->At(endIndex);
  268.         do {
  269.             iobj= this->At(i);            
  270.             while (i < j && CompareItems( iobj, endobj) <= 0) 
  271.                 iobj= this->At(++i);            
  272.             jobj= this->At(j);
  273.             while (j > i && CompareItems( jobj, endobj) >= 0) 
  274.                 jobj= this->At(--j);
  275.             if (i<j) {    // swap
  276.                 this->ReplaceItemsAt(i, &jobj, 1); //was &     
  277.                 this->ReplaceItemsAt(j, &iobj, 1); //was &     
  278.                 }
  279.         } while (i < j);
  280.         
  281.          this->ReplaceItemsAt(i, &endobj, 1);  
  282.         this->ReplaceItemsAt(endIndex, &iobj, 1);  
  283.         if (i - beginIndex < endIndex - i) {
  284.             QuickSort( beginIndex, i-1, CompareItems);
  285.           QuickSort( i+1, endIndex, CompareItems);
  286.           }
  287.         else {
  288.             QuickSort( i+1, endIndex, CompareItems);
  289.              QuickSort( beginIndex, i-1, CompareItems);
  290.              }
  291.         }
  292. }
  293.  
  294. long DList::QSPartition(long beginIndex, long endIndex,     
  295.                                    CompareFunc CompareItems)
  296. {
  297.     return 0;
  298. }
  299.  
  300. long DList::QSRandomPartition(long beginIndex, long endIndex,     
  301.                                    CompareFunc CompareItems)
  302. {
  303.     return 0;
  304. }
  305.  
  306.  
  307. #else
  308. // this was Apple's algorithm
  309.  
  310. void DList::QuickSort(long beginIndex, long endIndex, CompareFunc CompareItems)
  311. {
  312.     if (beginIndex < endIndex) {
  313.         long left = this->QSRandomPartition(beginIndex, endIndex, CompareItems);
  314.         this->QuickSort(beginIndex, left, CompareItems);
  315.         this->QuickSort(left+1, endIndex, CompareItems);     
  316.     }
  317. } 
  318.  
  319.  
  320. long DList::QSPartition(long beginIndex, long endIndex, CompareFunc CompareItems)
  321. {
  322.     if (beginIndex >= endIndex)
  323.         return endIndex;
  324.     {
  325.         DObjectPtr pivot = this->At(beginIndex);                // x
  326.         long i = beginIndex - 1;    // p - 1
  327.         long j = endIndex + 1;    // r + 1
  328.         while (true)
  329.         {
  330.             DObjectPtr secondKey;
  331.             do
  332.             {
  333.                 --j;
  334.                 secondKey = this->At(j);    // A[j]
  335.             } while (CompareItems( pivot, secondKey) <= -1);
  336.             do
  337.             {
  338.                 ++i;
  339.                 secondKey = this->At(i);    // A[i]
  340.             } while (CompareItems( pivot, secondKey) >= 1);
  341.             if (i < j)
  342.             {    // Swap the Items
  343.                 DObjectPtr leftObject = this->At(i);
  344.                 DObjectPtr rightObject = this->At(j);
  345.                 this->ReplaceItemsAt(i, &rightObject, 1); // was &
  346.                 this->ReplaceItemsAt(j, &leftObject, 1); //was &
  347.             }
  348.             else
  349.                 return j;
  350.         }
  351.     }
  352. } 
  353.  
  354.  
  355. long RandomArrayIndex(long beginIndex, long endIndex)
  356. {
  357.     if (beginIndex == endIndex) return beginIndex;
  358.     //long randomValue = rand() % labs(endIndex - beginIndex);// labs() not found by g++
  359.     long randomValue = endIndex - beginIndex;
  360.     if (randomValue < 0) randomValue = -randomValue;
  361.     randomValue= rand() % randomValue;
  362.     return beginIndex + randomValue;
  363. }
  364.  
  365. long DList::QSRandomPartition(long beginIndex, long endIndex, CompareFunc CompareItems )
  366. {
  367.     long i = RandomArrayIndex(beginIndex, endIndex);
  368.     
  369.     // exchange
  370.     DObjectPtr beginIndexObject = this->At(beginIndex);
  371.     DObjectPtr ithObject = this->At(i);
  372.     this->ReplaceItemsAt(beginIndex, &ithObject, 1); //was &    // A[beginIndex] = A[i]
  373.     this->ReplaceItemsAt(i, &beginIndexObject, 1); //was &    // A[i] = A[beginIndex]
  374.  
  375.     return this->QSPartition(beginIndex, endIndex, CompareItems);
  376. } 
  377.  
  378. #endif
  379.  
  380.  
  381. void DList::Sort()
  382. {
  383.     if (this->GetSize() > 0)
  384.         this->QuickSort(0, fSize-1, fCompareFunc); // was 1,fsize
  385. } 
  386.  
  387. void DList::SortBy(CompareFunc CompareItems)
  388. {
  389.     if (this->GetSize() > 0)
  390.         this->QuickSort(0, fSize-1, CompareItems); // was 1,fsize
  391. } 
  392.  
  393.  
  394. void DList::AtDelete(long index)
  395. {
  396.     if (fDeleteObjects)  At(index)->suicide(); //delete At(index); 
  397.         // ^^ this will make a mess of Pop() and Dequeue() method results, who call here
  398.     this->DeleteItemsAt(index, 1);
  399. }
  400.  
  401. void DList::Delete(DObject* item)
  402. {
  403.     long index;
  404.     if (item == NULL) return;
  405.     index = this->GetIdentityItemNo(item);
  406.     if (index != kEmptyIndex) this->AtDelete(index);
  407. } 
  408.  
  409.  
  410. DObject* DList::First()
  411. {
  412.     if (fSize <= kEmptySize)
  413.         return NULL;
  414.     else
  415.         return this->At(0); //1based: 1
  416. } 
  417.  
  418. DObject* DList::Last()
  419. {
  420.     if (fSize <= kEmptySize)
  421.         return NULL;
  422.     else
  423.         return this->At(fSize-1);
  424. }  
  425.  
  426.  
  427. long DList::GetIdentityItemNo(DObject* item)
  428. {
  429.     if (item == NULL) return kEmptyIndex;
  430.     long i, n= this->GetSize();
  431.     for (i= 0; i<n; i++) if (At(i) == item) return i;
  432.     return kEmptyIndex; 
  433. } 
  434.  
  435.  
  436. void DList::AtPut(long index, DObject* newItem)
  437. {
  438.     if (fOwnObjects && newItem) newItem->newOwner();
  439.     this->ReplaceItemsAt( index, &newItem, 1); //was &newItem
  440. } 
  441.  
  442.  
  443. void DList::InsertBefore(long index, DObject* item)
  444. {
  445.     if (fOwnObjects && item) item->newOwner();
  446.     this->InsertItemsBefore(index, &item, 1); // was &item !!!
  447. }
  448.  
  449.  
  450. void DList::InsertInOrder(DObject* item)
  451. {
  452.     long index= Search( fCompareFunc, &item);
  453.     if (index > kEmptyIndex)
  454.         InsertBefore( index, item);
  455.     else
  456.         InsertBefore( fSize, item);
  457. } 
  458.  
  459. void DList::InsertFirst(DObject* item)
  460. {
  461.     this->InsertBefore(0, item); //1
  462. } 
  463.  
  464. void DList::InsertLast(DObject* item)
  465. {
  466.     this->InsertBefore(fSize, item); // + 1
  467. } 
  468.  
  469.  
  470. void DList::Push(DObject* item)
  471. {
  472.     this->InsertLast(item);
  473. } 
  474.  
  475. DObject* DList::Pop()
  476. {
  477.     DObject* topOfStack;
  478.  
  479.     if (fSize <= kEmptySize)
  480.         topOfStack = NULL;
  481.     else {
  482.         topOfStack = this->At(fSize-1);
  483.         //this->AtDelete(fSize-1);
  484.         this->DeleteItemsAt(fSize-1, 1);     // this bypasses fDeleteObjects check ...
  485.         }
  486.     return topOfStack;
  487. } 
  488.  
  489.  
  490.  
  491. void DList::Queue(DObject* item)
  492. {
  493.     this->InsertLast(item);
  494. } 
  495.  
  496. DObject* DList::Dequeue()
  497. {
  498.     DObject* beginningOfStack;
  499.  
  500.     if (fSize <= kEmptySize)
  501.         beginningOfStack = NULL;
  502.     else {
  503.         beginningOfStack = this->At(0);    //1based: 1
  504.         //this->AtDelete(0);                 //1based: 1
  505.         this->DeleteItemsAt(0, 1);     // this bypasses fDeleteObjects check ...
  506.         }
  507.     return beginningOfStack;
  508. } 
  509.  
  510.  
  511.  
  512.  
  513.  
  514. DList*    FreeListIfObject(DList* aList)
  515. {
  516.     if (aList) {
  517.         //aList->FreeAllObjects(); // destructor now calls FreeAllObjects()
  518.         delete aList; 
  519.         }
  520.     return NULL;
  521. }
  522.